// 给定两个二叉树p和q,判断这两棵树是否相同，两棵树相同的定义: 结构上相同,节点具有相同的值

// 思路：后序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function isSameTree(p, q) {
    if (!p && !q) {
        return true
    }
    if (!p || !q) {
        return false
    }
    // 这里如果不相等，直接返回false，否则继续递归判断
    if (p.val !== q.val) {
        return false
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

const root1 = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};
const root2 = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

console.log(isSameTree(root1, root2))